//
//  FLinkedItem.m
//  FFoundation
//
//  Created by 三井 on 2021/6/30.
//

#import "FLinkedItem.h"

@implementation FLinkedItem

+ (instancetype)itemWithData:(id)data {
    FLinkedItem *item = [[FLinkedItem alloc] init];
    item.data = data;
    return item;
}

- (NSString *)description
{
    return [NSString stringWithFormat:@"this: %@, pre: %@, nxt: %@\n", self.data, self.li_pre.data, self.li_nxt.data];
}

@end

#pragma mark -
@interface FLinkedList ()

@end

@implementation FLinkedList

+ (instancetype)listWithObject:(id)object {
    FLinkedList *list = [[FLinkedList alloc] init];
    [list append:object];
    return list;
}

- (instancetype)init
{
    self = [super init];
    if (self) {
        _head = [FLinkedItem itemWithData:[NSNull null]];
        _tail = _head;
    }
    return self;
}

- (id)objectAtIndex:(NSUInteger)index {
    return [self itemAtIndex:index].data;
}

- (void)append:(id)object {
    FLinkedItem *item = [FLinkedItem itemWithData:object];
    [self insertItem:item after:self.tail];
}

- (id)remove:(id)object {
    for (FLinkedItem *p = self.head; p.li_nxt; p = p.li_nxt) {
        if ([p.data isEqual:object]) {
            return [self removeItem:p];
        }
    }
    return nil;
}

- (id)removeAt:(NSInteger)index {
    FLinkedItem *item = [self itemAtIndex:index];
    return [self removeItem:item];
}

- (void)reverse {
    FLinkedItem *p = self.head.li_nxt;
    if (!p) {
        return;
    }
    
    do {
        FLinkedItem *nxt = p.li_nxt;
        p.li_nxt = p.li_pre;
        p.li_pre = nxt;
        
        p = nxt;
    } while (p.li_nxt);
    
    p.li_nxt = p.li_pre;
    p.li_pre = _head;
    
    _tail = self.head.li_nxt;
    _tail.li_nxt = nil;
    _head.li_nxt = p;
}

#pragma mark -

- (FLinkedItem *)itemAtIndex:(NSUInteger)index {
    NSInteger i = 0;
    for (FLinkedItem *p = self.head.li_nxt; p; p = p.li_nxt) {
        if (index == i++) {
            return p;
        }
    }
    return nil;
}

- (FLinkedItem *)removeItem:(FLinkedItem *)item {
    for (FLinkedItem *p = self.head.li_nxt; p; p = p.li_nxt) {
        if ([p isEqual:item]) {
            p.li_pre.li_nxt = p.li_nxt;
            p.li_nxt.li_pre = p.li_pre;
            self.length--;
            return p;
        }
    }
    return nil;
}

- (void)insert:(id)object before:(NSUInteger)index {
    FLinkedItem *item = [self itemAtIndex:index];
    [self insertItem:[FLinkedItem itemWithData:object] before:item];
}

- (void)insertItem:(FLinkedItem *)item before:(FLinkedItem *)before {
    item.li_nxt = before;
    item.li_pre = before.li_pre;
    
    before.li_pre = item;
    item.li_pre.li_nxt = item;
    
    self.length++;
}

- (void)insertItem:(FLinkedItem *)item after:(FLinkedItem *)after {
    item.li_pre = after;
    item.li_nxt = after.li_nxt.li_nxt;
    
    after.li_nxt = item;
    item.li_nxt.li_pre = item;
    
    self.length++;
    
    if ([self.tail isEqual:after]) {
        _tail = self.tail.li_nxt;
    }
}

- (void)sort:(NSComparator)compare {
    [self sortFast:self.head.li_nxt length:self.length compare:compare];
}

- (NSString *)description
{
    NSMutableString *mStr = [NSMutableString stringWithFormat:@"List Length: %ld\n", self.length];
    for (FLinkedItem *p = self.head; p; p = p.li_nxt) {
        if ([p isEqual:self.head]) {
            [mStr appendString:@"Head > "];
        } else if ([p isEqual:self.tail]) {
            [mStr appendString:@"Tail > "];
        } else {}
        [mStr appendFormat:@"%@", p];
    }
    return mStr;
}

#pragma mark - private
- (void)sortFast:(FLinkedItem *)first length:(NSUInteger)len compare:(NSComparator)compare {
    if (!first || len <= 1) {
        return;
    }
    
    FLinkedItem *p = first.li_nxt;
    FLinkedItem *last = first;
    for (NSInteger i = 0; i < len; i++) {
        last = last.li_nxt;
    }
    
    NSUInteger littlers = 0;
    NSUInteger greaters = 0;
    while (p && ![p isEqual:last]) {
        FLinkedItem *next = p.li_nxt;
        if (compare(first, p) == NSOrderedDescending) {
            // item 大，将p移到前面
            [self removeItem:p];
            [self insertItem:p before:first];
            littlers++;
        } else {
            greaters++;
        }
        p = next;
    }
    
    [self sortFast:self.head.li_nxt length:littlers compare:compare];
    [self sortFast:first.li_nxt length:greaters compare:compare];
}
@end
